
package main.new_2024.month_02;


import main.dataStruct.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description: todo 106. 从中序与后序遍历序列构造二叉树
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0221 {

    //前序 第一个得到根结点，中序 区分左右子树，左右递归， 后续，最后一个是根节点
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        Map<Integer, Integer> index = new HashMap<>(n); // 预分配空间
        for (int i = 0; i < n; i++) {
            index.put(inorder[i], i);
        }
        return dfs(inorder, 0, n, postorder, 0, n, index); // 左闭右开区间
    }
    private TreeNode dfs(int[] inorder, int inL, int inR, int[] postorder, int postL, int postR, Map<Integer, Integer> index) {
        if (postL == postR) { // 空节点
            return null;
        }
        int leftSize = index.get(postorder[postR - 1]) - inL; // 左子树的大小
        TreeNode left = dfs(inorder, inL, inL + leftSize, postorder, postL, postL + leftSize, index);
        TreeNode right = dfs(inorder, inL + leftSize + 1, inR, postorder, postL + leftSize, postR - 1, index);
        return new TreeNode(postorder[postR - 1], left, right);
    }

}

